package com.lims;

import java.util.*;

/**
 * 数独算法
 * @author Mr li
 *
 */
public class 数独算法 {
    //将数组分成九个宫，记录每个宫的横纵初始横纵坐标
    Map<Integer,Integer> row = new HashMap<Integer,Integer>();
    Map<Integer,Integer> line = new HashMap<Integer,Integer>();
    //数独数组长度
    static int le = 9;
    //一个坐标允许填的所有值
    static int aRow[] = {1,2,3,4,5,6,7,8,9};
    //初始化数组
    static int sudoku[][] = new int[le][le];
    //获取数独数组中所有为0的位置的坐标，并且存入一个map中
    TreeSet<String> zeroCoord = new TreeSet<String>();

    //thirdSolution方法需要
    static int testSudoku[][] = new int[le][le];
    static int isOk = 1;

    /**
     * 位解：排除法，根据该坐标获取该坐标行，列，宫的所有数字，然后排除掉，如果该此时剩余唯一一个值，表示这个值为数独解
     * @param sudoku 传入的数独数组
     * @param zeroCoord 数组中为0的坐标，即需要解的所有坐标集
     * @return
     */
    public int firstSolution(int[][] sudoku,TreeSet<String> zeroCoord){
        System.out.println("firstSolution---start");
        //获取“0”的个数
        int zeroNum = zeroCoord.size();
        //转为数组再进行处理
        Object[] zCoord = zeroCoord.toArray();
        for(int i=0;i<zCoord.length;i++){
            String[] rlArr = zCoord[i].toString().split(",");
            int ro = Integer.parseInt(rlArr[0]);
            int li = Integer.parseInt(rlArr[1]);
            TreeSet<Integer> numCanSet = new TreeSet<Integer>();
            numCanSet = this.getNumCanSet(sudoku,ro,li);//根据坐标获取该坐标可填入的数组集
            if(numCanSet.size() == 1){
                sudoku[ro][li] = numCanSet.first();
                zeroCoord.remove(ro+","+li);//如果该坐标获取到解，则移除该坐标
                System.out.println("坐标：("+ro+","+li+") 值："+numCanSet.first()+"剩余"+zeroCoord.size());//记录每次解值的坐标以及该坐标的值
            }else if(numCanSet.size() == 0){
                return -1;//出现悖论位
            }
        }
        System.out.println("firstSolution---end");
        if(zeroCoord.size() == zeroNum){
            return 0;//本次过程没有获得一个解
        }
        return 1;
    }
    /**
     * 宫解：首先遍历一个宫内的九个坐标，并且获取每个坐标可填入的所有值，然后判断在本宫内，哪个值只出现了一次，表示该值只可以填入该坐标
     * @param sudoku 传入的数独数组
     * @param zeroCoord 数组中为0的坐标，即需要解的所有坐标集
     * @return
     */
    public int secondSolution(int[][] sudoku,TreeSet<String> zeroCoord){
        System.out.println("secondSolution---start");
        //获取“0”的个数
        int zeroNum = zeroCoord.size();
        for(int i=0;i<le;i++){
            //存入每个宫里面的1到9还没有填入的数字，并且存入，每个数字在本宫内可填入几次，如果是一次，表示获取到一个解
            Map<Integer,Integer> canInNum = new HashMap<Integer,Integer>();
            //存入每个宫里面的1到9还没有填入的数字，并且存入，遍历之下，每个数字可填入的最新坐标，然而我们依然只关心只有一个值的解，那么其坐标只存入一次
            Map<Integer,String> newCoord = new HashMap<Integer,String>();
            //获取宫的初始坐标
            int rowF = row.get(i);
            int lineF = line.get(i);
            //循环遍历宫内九个坐标
            for(int m=0;m<3;m++){
                for(int n=0;n<3;n++){
                    //每个坐标可填入的值的集
                    TreeSet<Integer> setCan = new TreeSet<Integer>();
                    int num = sudoku[rowF+m][lineF+n];
                    if(num == 0){
                        setCan = this.getNumCanSet(sudoku,rowF+m,lineF+n);
                        if(setCan.size() == 0){
                            return -1;//出现悖论位
                        }
                        for(int a : setCan){
                            try {
                                canInNum.put(a, canInNum.get(a)+1);
                            } catch (Exception e) {
                                canInNum.put(a, 1);
                            }
                            newCoord.put(a, (rowF+m)+","+(lineF+n));
                        }
                    }
                }
            }
            //遍历canInNum，获取只出现一次的值，以及该值的坐标
            for(int key : canInNum.keySet()){
                if(canInNum.get(key) == 1){
                    String coord = newCoord.get(key);
                    String[] coordArr = coord.split(",");
                    int ro = Integer.parseInt(coordArr[0]);
                    int le = Integer.parseInt(coordArr[1]);
                    //将值填入数组中，同时将zeroNum减1
                    sudoku[ro][le] = key;
                    zeroCoord.remove(ro+","+le);
                    System.out.println("坐标：("+ro+","+le+") 值："+key+"剩余"+zeroCoord.size());
                }
            }
        }
        System.out.println("secondSolution---end");
        if(zeroCoord.size() == zeroNum){
            return 0;//本次过程没有获得一个解
        }
        return 1;
    }
    /**
     * 双值位测解：获取某个只可以填入两个值的坐标，然后分别将此值填入其中，并继续解此数独，如果其中一个值填入数独中，出现错误，则可以确定另外一个值为正确值
     * @param sudoku 传入的数独数组
     * @param zeroCoord 数组中为0的坐标，即需要解的所有坐标集
     * @return
     */
    public int thirdSolution(int[][] sudoku,TreeSet<String> zeroCoord){
        System.out.println("thirdSolution---start");
        //获取“0”的个数
        int zeroNum = zeroCoord.size();
        Object[] zCoord = zeroCoord.toArray();
        for(int i=0;i<zCoord.length;i++){
            String[] rlArr = zCoord[i].toString().split(",");
            int ro = Integer.parseInt(rlArr[0]);
            int li = Integer.parseInt(rlArr[1]);
            TreeSet<Integer> numCanSet = new TreeSet<Integer>();
            numCanSet = getNumCanSet(sudoku,ro,li);//根据坐标获取该坐标可填入的数组集
            if(numCanSet.size() == 2){
                //建立一个set集，存放正确的坐标值
                TreeSet<Integer> trueSet = new TreeSet<Integer>();
                for(int q=0;q<2;q++){
                    TreeSet<String> testZeroCoord = new TreeSet<String>();
                    //测试数组建立
                    int testSudoku[][] = new  int[sudoku.length][sudoku.length];
                    for(int m=0;m<sudoku.length;m++){
                        for(int n=0;n<sudoku[m].length;n++){
                            testSudoku[m][n] = sudoku[m][n];
                        }
                    }
                    int a = (int) numCanSet.toArray()[q];
                    testSudoku[ro][li] = a;
                    //调用测试方法，如果为1表示改值可填入，当然，如果最后两值判断都正确，则忽略该坐标，继续下一坐标
                    testZeroCoord.addAll(zeroCoord);
                    testZeroCoord.remove(ro+","+li);
                    int r = this.isOk(testSudoku,testZeroCoord);
                    if(r == 1){
                        trueSet.add(a);
                    }
                    if(r == -1){
                        return -1;
                    }
                }
                //集长度为1，表示获取到正确解值
                if(trueSet.size() == 1){
                    int a = trueSet.first();
                    sudoku[ro][li] = a;
                    zeroCoord.remove(ro+","+li);
                    System.out.println("成功"+numCanSet.size()+"值位("+ro+","+li+")，值为："+a+",剩余"+zeroCoord.size());
                }else{
                    System.out.println("失败"+numCanSet.size()+"值位("+ro+","+li+")，值集为："+numCanSet);
                }
            }

        }
        System.out.println("thirdSolution---end");
        if(zeroCoord.size() == zeroNum){
            return 0;
        }
        return 1;
    }
    /**
     * 获取该坐标可输入值集合，并返回
     * @param ro 行坐标
     * @param li 列坐标
     * @return
     */
    public TreeSet<Integer> getNumCanSet(int[][] sudoku,int ro,int li){
        TreeSet<Integer> setNo = new TreeSet<Integer>();
        TreeSet<Integer> setCan = new TreeSet<Integer>();
        //行数组
        int row[] = sudoku[ro];
        for(int i=0;i<le;i++){
            if(row[i] != 0){
                setNo.add(row[i]);
            }
        }
        //列处理
        for(int j=0;j<le;j++){
            if(sudoku[j][li] != 0){
                setNo.add(sudoku[j][li]);
            }
        }
        //宫处理
        int r = ro/3*3;//宫的初始行坐标
        int l= li/3*3;//宫的初始列坐标
        for(int m=0;m<3;m++){
            for(int n=0;n<3;n++){
                if(sudoku[r+m][l+n] != 0){
                    setNo.add(sudoku[r+m][l+n]);
                }
            }
        }
        Object[] judgeArr = setNo.toArray();
        for(int a : aRow){
            boolean isA = true;
            for(Object b : judgeArr){
                if((int) b == a){
                    isA = false;
                    break;
                };
            }
            if(isA){
                setCan.add(a);
            }
        }
        return setCan;
    }
    /**
     * 宫的横纵初始坐标
     */
    public void rLInitialCoord(){
        //该循环表示九个宫的初始坐标都会分别存入row与line中，i对应的是一到九宫
        for(int i=0;i<le;i++){
            if(i<3){
                row.put(i, 0);
                line.put(i, i*3);
            }else if(i<6){
                row.put(i, 3);
                line.put(i, i%3*3);
            }else{
                row.put(i, 6);
                line.put(i, i%6*3);
            }
        }
    }
    /**
     * 获取输入的数独，空值位用0表示，纯数字输入
     */
    public void getInSudoku(){
        @SuppressWarnings("resource")
        Scanner sc = new Scanner(System.in);
        String sudokuIn = sc.next();
        if(sudokuIn.length() != 81){//判断输入的数组是否正确
            System.out.println("请输入正确的数组");
        }else{
            for(int i=0;i<le;i++){//遍历纯数字字符串，并且插入数独数组中
                for(int j=0;j<le;j++){
                    int n = Integer.parseInt(sudokuIn.substring(le*i+j,le*i+j+1));
                    sudoku[i][j] = n;
                }
            }
        }
    }
    /**
     * 获取数独数组中所有为0的位置的坐标，并且存入一个map中,初始化zeroNum的值
     */
    public void getAllZeroNumCoord(){
        for(int i=0;i<le;i++){
            for(int j=0;j<le;j++){
                if(sudoku[i][j] == 0){
                    zeroCoord.add(i+","+j);
                }
            }
        }
    }
    /**
     * 打印数独结果
     */
    public void printSudoku(int[][] sudoku){
        for(int i=0;i<le;i++){
            int pr[] = sudoku[i];
            System.out.println(Arrays.toString(pr));
        }
    }
    /**
     * 递归函数
     */
    public void recursion(){
        int isSuccess = this.callBack();
        if(isSuccess == 1){
            this.recursion();
        }else{
            return;
        }
    }
    /**
     * 递归函数中调用，返回1表示数独解成功，0表示还未完全解出，-1表示数独解失败
     * @return
     */
    public int callBack(){
        //为0的时候表示已经获取全部解，打印最终解
        if(zeroCoord.size() == 0){
            System.out.println("成功：");
            this.printSudoku(sudoku);
            return 0;
        }
        if(this.firstSolution(sudoku, zeroCoord) == 1){
            return 1;
        }else{
            if(this.secondSolution(sudoku, zeroCoord) == 1){
                return 1;
            }else{
                int thr = this.thirdSolution(sudoku, zeroCoord);
                if( thr == 1){
                    return 1;
                }else if(thr == -1){
                    System.out.println("成功：");
                    this.printSudoku(testSudoku);
                    return 0;
                }else{
                    System.out.println("失败：");
                    this.printSudoku(sudoku);
                    return -1;
                }
            }
        }
    }
    /**
     * 判断数独是否出现悖论位
     * 0出现，1无错，-1填入测试值直接完成解数独
     * @return
     */
    public int isOk(int[][] sudoku,TreeSet<String> zeroCoord) {
        //将测试数据的初始化
        for(int m=0;m<le;m++){
            for(int n=0;n<le;n++){
                testSudoku[m][n] = sudoku[m][n];
            }
        }
        isOk = 1;
        this.testRecursion(zeroCoord);
        return isOk;
    }
    /**
     * 递归函数
     */
    public void testRecursion(TreeSet<String> testZeroCoord){
        int isSuccess = this.testCallBack(testZeroCoord);
        if(isSuccess == 1){
            this.testRecursion(testZeroCoord);
        }else{
            return;
        }
    }
    /**
     * 递归函数中调用，返回1表示数独解成功，0表示还未完全解出，-1表示数独解失败
     * @return
     */
    public int testCallBack(TreeSet<String> testZeroCoord){
        //为0的时候表示已经获取全部解，打印最终解
        if(testZeroCoord.size() == 0){
            isOk = -1;
            return -1;
        }else{
            int fir = this.firstSolution(testSudoku, testZeroCoord);
            if(fir == 1){
                return 1;
            }else{
                if(fir == 0){
                    int sec = this.secondSolution(testSudoku, testZeroCoord);
                    if(sec == 1){
                        return 1;
                    }else{
                        if(sec == -1){
                            isOk = 0;
                            return 0;
                        }
                    }
                }else{
                    isOk = 0;
                    return 0;
                }
            }
        }
        return 0;
    }
    /**
     * main方法测试
     * @param args
     */
    public static void main(String[] args) {

        数独算法 sd = new 数独算法();
        //获取输入的数独数组
        sd.getInSudoku();
        //初始化数独需要填入的总个数以及其坐标
        sd.getAllZeroNumCoord();
        //宫的横纵初始坐标
        sd.rLInitialCoord();
        //递归函数解数独开始
        sd.recursion();
        System.exit(0);
    }
}
